package string;

/**
 * 一个由括号组成的字符串，添加多少个括号才能组成一个合法的括号字符串
 *
 * @author Liaorun
 */
public class NeedParentheses {

    public static void main(String[] args) {
        System.out.println(needParentheses("((((("));
        System.out.println(needParentheses(")))"));
    }

    public static int needParentheses(String str) {
        // 记录需要的右括号 既是 还有多少左括号没有对应,默认值0
        int t = 0;
        // 记录需要的左括号，默认值0
        int needSolveRight = 0;

        for (int i = 0; i < str.length(); i++) {

            if (str.charAt(i) == '(') {
                // 遇到左括号，需要添加的右括号+1
                // e: str = ")(", i = 1, t = 0(没有左括号没有对应的右括号), needSolveRight = 1(有一个右括号没有对应的左括号)
                t++;
                // t = 1(还有1个左括号没有对应的右括号)
            } else {
                // 遇到右括号
                if (t == 0) {
                    // 没有对应的左括号需要添加
                    // e: str = ")",i = 0(第1次循环), t = 0(没有左括号没有对应的右括号), needSolveRight = 0(没有右括号没有对应的左括号)
                    needSolveRight++;
                    // needSolveRight = 1(需要添加一个左括号和当前位置的右括号成对)
                } else {
                    // 有匹配的左括号，需要添加的右括号数目-1
                    // e: str = "(()",i = 2(第3次循环), t = 2(还有2个左括号没有对应的右括号), needSolveRight = 0(没有右括号没有对应的左括号)
                    t--;
                    // t = 1(还有1个左括号没有对应的右括号)
                }
            }
        }

        // 返回需要添加的括号总数
        return t + needSolveRight;
    }
}
